We study the problem of 0nding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to 0nding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to 0nd an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.
展开▼
